using System.Text;

namespace array_demo.Model
{
    // 链表数据结构（单链表）
    // 链表作用为了解决数组动态容量的问题
    public class LinkedList1<E>
    {
        /// <summary>
        /// 定义节点对象
        /// </summary>
        private class Node
        {
            // 当前的元素
            public E e;

            // 当前指向下一个节点的引用
            public Node next;

            /// <summary>
            ///初始化构造函数
            /// </summary>
            /// <param name="e"></param>
            /// <param name="next"></param>
            public Node(E e, Node next)
            {
                this.e = e;
                this.next = next;
            }

            /// <summary>
            /// 初始化构造函数 不指定下一级别
            /// </summary>
            /// <param name="e"></param>
            public Node(E e)
            {
                this.e = e;
                this.next = null;
            }

            public override string ToString()
            {
                return e.ToString();
            }
        }

        /// <summary>
        /// 头结点
        /// </summary>
        private Node head;


        /// <summary>
        /// 链表中的元素个数
        /// </summary>
        private int N;

        public LinkedList1()
        {
            head = null;
            N = 0;
        }

        public int count
        {
            get { return N; }
        }

        public bool isEmpty
        {
            get { return N == 0; }
        }

        public void AddNode(int index, E e)
        {
            if (index < 0 || index > N)
            {
                throw new AggregateException("数组索引越界");
            }
            if (index == 0)
            {
                // 创建一个node节点
                Node node = new Node(e);
                // 先将node节点指向一个之前的头结点
                node.next = head;
                // 将head指向node节点
                head = node;
            }
            else
            {
                //创建一个节点
                Node pre = head;
                // 将head移动索引减1次
                for (int i = 0; i < index - 1; i++)
                    pre = pre.next;
                Node node = new Node(e);
                node.next = pre.next;
                pre.next = node;
            }
            N++;
        }

        public void AddFirst(E e)
        {
            AddNode(0, e);
        }


        public void AddLast(E e)
        {
            AddNode(N, e);
        }


        public E GetIndex(int index)
        {
            if (index < 0 || index > N)
            {
                throw new AggregateException("数组索引越界");
            }

            Node current = head;
            // 一步步移动到指定的节点，返回节点的值
            for (int i = 0; i < index; i++)
                current = current.next;
            return current.e;
        }


        public E GetFirst()
        {
            return GetIndex(0);
        }


        public E GetLast()
        {
            return GetIndex(N - 1);
        }


        public void Set(int index, E e)
        {
            if (index < 0 || index > N)
            {
                throw new AggregateException("数组索引越界");
            }
            Node current = head;
            // 注意这里是从头节点开始到修改节点
            for (int i = 0; i < index; i++)
                current = current.next;

            current.e = e;
        }

        public bool IsContains(E e)
        {
            Node curr = head;
            while (curr != null)
            {
                if (curr.e.Equals(e))
                {
                    return true;
                }
                curr = curr.next;
            }
            return false;
        }

        public E deleteIndex(int index)
        {
            if (index < 0 || index >= N)
            {
                throw new AggregateException("数组索引越界");
            }

            if (index == 0)
            {
                Node deleteNode = head;
                head = head.next;
                N--;
                return deleteNode.e;
            }
            else
            {
                // 注意这里是从头节点开始到删除的前一位
                Node pre = head;
                for (int i = 0; i < index - 1; i++)
                    pre = pre.next;
                Node deleteNode = pre.next;
                pre.next = deleteNode.next;
                N--;
                return deleteNode.e;
            }
        }

        public  E deleteLast()
        {
           return deleteIndex(N-1);
        }


        public  E deleteFirst()
        {
           return deleteIndex(0);
        }


        public void Remove(E e)
        {
            Node curr = head;
            Node pre = null;

            if (curr.e.Equals(e))
            {
                head = head.next;
                N--;
            }
            else
            {
                while (curr != null)
                {
                    // 判断是否找到了值
                    if (curr.e.Equals(e))
                        break;
                    // 如果没有,移动到下一个节点并将值存在pre里面
                    pre=curr;
                    curr=curr.next;
                }

                // 说明找到了这个元素
               if(curr!=null)
               {
                   // 
                   pre.next=pre.next.next;
                   N--;
               }
            }

        }


        /// <summary>
        /// 重写转字符串
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder stringBuilder = new StringBuilder();
            Node curr = head;
            while (curr != null)
            {
                stringBuilder.Append(curr + "->");
                curr = curr.next;
            }
            stringBuilder.Append("null");
            return stringBuilder.ToString();
        }
    }
}